package com.algrithom.bfs;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Objects;
import java.util.Queue;
import java.util.Set;

/**
 * 课程表II
 */
public class Solution5 {
    
    public static void main(String[] args){
        int[][] prerequisites = {{1,0},{2,0},{3,1},{3,2}};
        int numCourses = 4;
        System.out.println(Arrays.toString(findOrder(numCourses,prerequisites)));
        System.out.println(Arrays.toString(findOrder2(numCourses,prerequisites)));
    }
    
    public static int[] findOrder(int numCourses,int[][] prerequisites){
        if (numCourses <= 0) {
            return new int[0];
        }
        // key->value:vlue依赖key
        Map<Integer,Set<Integer>> adj = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            adj.put(i,new HashSet<>());
        }
        // 记录入度情况
        int[] inDegree = new int[numCourses];
        for (int[] p : prerequisites) {
            adj.get(p[1]).add(p[0]);
            inDegree[p[0]]++;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int[] res = new int[numCourses];
        // 当前结果集列表里的元素个数，正好可以作为下标
        int count = 0;
        
        while (!queue.isEmpty()) {
            // 当前入度为 0 的结点
            Integer head = queue.poll();
            res[count++] = head;
            
            Set<Integer> successors = adj.get(head);
            for (Integer nextCourse : successors) {
                inDegree[nextCourse]--;
                // 马上检测该结点的入度是否为 0，如果为 0，马上加入队列
                if (inDegree[nextCourse] == 0) {
                    queue.offer(nextCourse);
                }
            }
        }
        
        // 如果结果集中的数量不等于结点的数量，就不能完成课程任务，这一点是拓扑排序的结论
        if (count == numCourses) {
            return res;
        }
        return new int[0];
    }
    
    public static int[] findOrder2(int numCourses,int[][] prerequisites){
        if (numCourses <= 0) {
            return new int[0];
        }
        Map<Integer,Set<Integer>> map = new HashMap<>();
        int[] indegree = new int[numCourses];
        for (int[] course : prerequisites) {
            if (!map.containsKey(course[1])) {
                Set<Integer> set = new HashSet<>();
                set.add(course[0]);
                map.put(course[1],set);
                indegree[course[0]]++;
            } else {
                Set<Integer> set = map.get(course[1]);
                set.add(course[0]);
                map.put(course[1],set);
                indegree[course[0]]++;
            }
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int index = 0; index < indegree.length; index++) {
            if (indegree[index] == 0) {
                queue.offer(index);
            }
        }
        int[] result = new int[numCourses];
        int count = 0;
        while (!queue.isEmpty()) {
            int index = queue.poll();
            Set<Integer> set = map.get(index);
            result[count++] = index;
            if (Objects.isNull(set)) {
                continue;
            }
            for (Integer val : set) {
                indegree[val]--;
                if (indegree[val] == 0) {
                    queue.offer(val);
                }
            }
        }
        if (count == numCourses) {
            return result;
        }
        return new int[0];
    }
}
